package main

import "fmt"

/*
你是一个专业的小偷，计划偷窃沿街的房屋。
每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，
计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
*/

/*
大白话：从数组中拿数，不能拿任何两个相邻的；问：能拿出的最大数据和是多少。
解题思路：
	可怜的小偷，每遇到一户，都要考虑一下偷还是不偷（不能偷、不愿偷）
	那么，小偷可以先根据掌握的情况，把所有能偷的组合都列出来，再看哪种组合的利益最大。

[1,2,3,1]
动态规划表达式：
	f(i,b): 表示第i家偷盗状态为b时，能获取的最大利润，b:0-不偷；1-偷

	f(0,0)=0；						第0家不偷能获取的最大利润为0；
	f(0,1)=1；						第0加偷，能获取的最大利润为1；
	f(1,0)=max{f(0,0),f(0,1)}=1；	表示第1家不偷，能获取最大利润的情况是：上一家偷或者不偷最大利润中的最大的值；
	f(1,1)=f(0,0)+2；				第1家偷，那么上一家就不能偷，表现为上一家不偷的最大获利 + 本地偷的值；
	f(2,0)=max{f(1,0),f(1,1)}=2；	反正这次不偷，上一次偷不偷都能到这个状态，所以选上一次偷或者不偷的最大值；
	f(2,1)=f(1,0)+3=4；				上次不偷+本次偷的组合；
	f(3,0)=max{f(2,0),f(2,1)}=4；
	f(3,1)=f(2,0)+1=3；

	最终，能获取的最大盗资为：4；
	过程为：f(3,0)<-f(2,1)<-f(1,0)<-f(0,1) ----- 0,3,0,1

动态规划方程：
	f(i,0) = max(f(i-1,0),f(i-1,1))
	f(i,1) = f(i-1,0)+nums[i]
*/

func rob1(nums []int) int {
	l := len(nums)
	f := make([][2]int, l)
	for i := range nums {
		if i == 0 {
			f[i][0] = 0
			f[i][1] = nums[i]
			continue
		}

		f[i][0] = max(f[i-1][0], f[i-1][1])
		f[i][1] = f[i-1][0] + nums[i]
	}
	return max(f[l-1][0], f[l-1][1])

}

/*
优化：

	还是关于空间复杂度的优化，每次只是基于前一次的结果计算，只要一组空间循环利用就可以了
*/
func rob2(nums []int) int {
	f := [2]int{}
	for i := range nums {
		if i == 0 {
			f[0] = 0
			f[1] = nums[i]
			continue
		}
		f[0], f[1] = max(f[0], f[1]), f[0]+nums[i]
	}
	return max(f[0], f[1])
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	nums := []int{1, 2, 3, 1}
	fmt.Println(rob1(nums))
	fmt.Println(rob2(nums))
}
